package com.arron.algorithm.leetcodetop100.二叉树;

import com.arron.algorithm.tree.TreeNode;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;

/**
 * 652. 寻找重复的子树
 * 中等
 */
public class FindDuplicateSubtrees {


        HashMap<String,Integer> map = new HashMap<>();
        List<TreeNode> treeNodes = new ArrayList<>();
    public List<TreeNode> findDuplicateSubtrees(TreeNode root) {

        dfs(root);

        return treeNodes;
    }

    //    二叉树:       2
    //                / \
    //               1   11
    //              / \    \
    //             11   5   1
    private String dfs(TreeNode root) {

        if (root == null){
            return "#";
        }

        StringBuffer stringBuffer = new StringBuffer();
        stringBuffer
                .append(root.val)
                .append("_") // 防止出现 父节点和子节点调换顺序的子树相同，如上二叉树
                .append(dfs(root.left))
                .append(dfs(root.right));


        String s = stringBuffer.toString();
        map.put(s,map.getOrDefault(s,0)+1);
        if (map.get(s)!=null && map.get(s)==2){
            treeNodes.add(root);
        }

        return s;
    }
}
